# include "jam.h"
# include "hash.h"

# define MAX_LISTS 32
# define ALIGNED(x) ( ( x + sizeof( ITEM ) - 1 ) & ~( sizeof( ITEM ) - 1 ) )

struct hashhdr {
  struct item *next;
  unsigned int keyval;
} ;

struct hashdata {
  char  *key;
} ;

typedef struct item {
  struct hashhdr hdr;
  struct hashdata data;
} ITEM ;

struct hash {
  struct {
    int nel;
    ITEM **base;
  } tab;

  int bloat;
  int inel;
  struct {
    int more;
    char *next;
    int datalen;
    int size;
    int nel;
    int list;

    struct {
      int nel;
      char *base;
    } lists[ MAX_LISTS ];
  } items;

  const char *name;
} ;

static void hashrehash( struct hash *hp );
static void hashstat( struct hash *hp );

int hashitem(
  register struct hash *hp,
  HASHDATA **data,
  int enter ) {
  ITEM **base;
  register ITEM *i;
  unsigned char *b = ( unsigned char * )( *data )->key;
  unsigned int keyval;
  if( enter && !hp->items.more ) {
    hashrehash( hp );
  }
  if( !enter && !hp->items.nel ) {
    return 0;
  }
  keyval = *b;
  while( *b ) {
    keyval = keyval * 2147059363 + *b++;
  }
  base = hp->tab.base + ( keyval % hp->tab.nel );
  for( i = *base; i; i = i->hdr.next )
    if( keyval == i->hdr.keyval &&
        !strcmp( i->data.key, ( *data )->key ) ) {
      *data = &i->data;
      return !0;
    }
  if( enter ) {
    i = ( ITEM * )hp->items.next;
    hp->items.next += hp->items.size;
    hp->items.more--;
    memcpy( ( char * )&i->data, ( char * )*data, hp->items.datalen );
    i->hdr.keyval = keyval;
    i->hdr.next = *base;
    *base = i;
    *data = &i->data;
  }
  return 0;
}

static void hashrehash( register struct hash *hp ) {
  int i = ++hp->items.list;
  hp->items.more = i ? 2 * hp->items.nel : hp->inel;
  hp->items.next = ( char * )malloc( hp->items.more * hp->items.size );
  hp->items.lists[i].nel = hp->items.more;
  hp->items.lists[i].base = hp->items.next;
  hp->items.nel += hp->items.more;
  if( hp->tab.base ) {
    free( ( char * )hp->tab.base );
  }
  hp->tab.nel = hp->items.nel * hp->bloat;
  hp->tab.base = ( ITEM ** )malloc( hp->tab.nel * sizeof( ITEM ** ) );
  memset( ( char * )hp->tab.base, '\0', hp->tab.nel * sizeof( ITEM * ) );
  for( i = 0; i < hp->items.list; i++ ) {
    int nel = hp->items.lists[i].nel;
    char *next = hp->items.lists[i].base;
    for( ; nel--; next += hp->items.size ) {
      register ITEM *i = ( ITEM * )next;
      ITEM **ip = hp->tab.base + i->hdr.keyval % hp->tab.nel;
      i->hdr.next = *ip;
      *ip = i;
    }
  }
}

struct hash * hashinit(
  int datalen,
  const char *name ) {
  struct hash *hp = ( struct hash * )malloc( sizeof( *hp ) );
  hp->bloat = 3;
  hp->tab.nel = 0;
  hp->tab.base = ( ITEM ** )0;
  hp->items.more = 0;
  hp->items.datalen = datalen;
  hp->items.size = sizeof( struct hashhdr ) + ALIGNED( datalen );
  hp->items.list = -1;
  hp->items.nel = 0;
  hp->inel = 11;
  hp->name = name;
  return hp;
}

void hashdone( struct hash *hp ) {
  int i;
  if( !hp ) {
    return;
  }
  if( DEBUG_MEM ) {
    hashstat( hp );
  }
  if( hp->tab.base ) {
    free( ( char * )hp->tab.base );
  }
  for( i = 0; i <= hp->items.list; i++ ) {
    free( hp->items.lists[i].base );
  }
  free( ( char * )hp );
}


static void hashstat( struct hash *hp ) {
  ITEM **tab = hp->tab.base;
  int nel = hp->tab.nel;
  int count = 0;
  int sets = 0;
  int run = ( tab[ nel - 1 ] != ( ITEM * )0 );
  int i, here;
  for( i = nel; i > 0; i-- ) {
    if( ( here = ( *tab++ != ( ITEM * )0 ) ) ) {
      count++;
    }
    if( here && !run ) {
      sets++;
    }
    run = here;
  }
  printf( "%s table: %d+%d+%d (%dK+%luK) items+table+hash, %f density\n",
          hp->name,
          count,
          hp->items.nel,
          hp->tab.nel,
          hp->items.nel * hp->items.size / 1024,
          hp->tab.nel * sizeof( ITEM ** ) / 1024,
          ( float )count / ( float )sets );
}
